package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * TODO
 * https://leetcode.com/problems/coin-change-2/discuss/99212/Knapsack-problem-Java-solution-with-thinking-process-O(nm)-Time-and-O(m)-Space
 * https://leetcode.com/problems/coin-change-2/discuss/99210/python-O(n)-space-dp-solution
 *
 * @author tzp
 * @since 2020/9/22
 */
public class LC518_2 implements DynamicProblem {
    /**
     *         """
     *         :type amount: int
     *         :type coins: List[int]
     *         :rtype: int
     *         """
     *         dp = [0] * (amount + 1)
     *         dp[0] = 1
     *         for i in coins:
     *             for j in range(1, amount + 1):
     *                if j >= i:
     *                    dp[j] += dp[j - i]
     *         return dp[amount]
     * */
}
